function [trellis_matrix, parity_matrix] = trellis(code_g);
% construction of a matrix representing the trellis from the 
% generator polynomials.
% When a 0 at the input change the state from i to j,
% then trellis_matrix(i,j) = -1 and parity_matrix(i,j)= 2*output-1
% When a 1 at the input change the state from i to j,
% then trellis_matrix(i,j) = 1 and parity_matrix(i,j)= 2*output-1
% When there is no path between state i and state j,
% then trellis_matrix(i,j) = 0 and parity_matrix(i,j)= 0
%
% We will use these two matrices in the decoders,
% to compute the transition probabilities (gammaK(s',s))


% code properties
[n,K] = size(code_g);
m = K - 1;
no_of_states = 2^m;

trellis_matrix= zeros(no_of_states);
parity_matrix= zeros(no_of_states);

for s=1: no_of_states

dec_cnt_s=s-1; i=1;

% decimal to binary state
while  dec_cnt_s >=0 & i<=m
       bin_cnt_s(i) = rem( dec_cnt_s,2) ;
       dec_cnt_s  = (dec_cnt_s-  bin_cnt_s(i))/2;
        i=i+1;   
end
bin_cnt_s=bin_cnt_s(m:-1:1);
   
% next state when input is 0
   a = rem( code_g(1,:)*[0 bin_cnt_s ]', 2 );
   v = code_g(2,1)*a;

   for j = 1:K-1
      v = xor(v, code_g(2,j+1)*bin_cnt_s(j));
   end;

nstate0 = [a  bin_cnt_s(1:m-1)];
% binary to decimal state
d=2.^(m-1:-1:0); 
j=nstate0*d'+1;
trellis_matrix(s,j)= -1;
parity_matrix(s,j)= 2*v-1;


% next state when input is 1
   a = rem( code_g(1,:)*[1 bin_cnt_s]', 2 );
   v = code_g(2,1)*a;

   for j = 1:K-1
      v = xor(v, code_g(2,j+1)*bin_cnt_s(j));
   end;

nstate1 = [a bin_cnt_s(1:m-1)];
d=2.^(m-1:-1:0); 
j=nstate1*d'+1;
trellis_matrix(s,j)= 1;
parity_matrix(s,j)= 2*v-1;
end







